package array;
//接雨水
public class leetcode42 {
    public static void main(String[] args) {
        int[] nums = {4,2,0,3,2,5};
        System.out.println(trap(nums));
    }

    public static int trap(int[] height) {
        int rain = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int max_left = height[0];
        int max_right = height[height.length - 1];
        left[0] = 0;
        right[height.length - 1] = 0;
        for (int i = 1; i < height.length; i++) {
            left[i] = Math.max(max_left, height[i]);
            if(height[i] > max_left) max_left = height[i];
            right[height.length-1-i] = Math.max(max_right, height[height.length - 1 - i]);
            if(height[height.length - 1 - i] > max_right) max_right = height[height.length - i - 1];
        }

        for (int i = 1; i < height.length - 1; i++) {
            rain += Math.min(left[i], right[i]) - height[i];
        }
        return rain;
    }
}
